"""
    python中队列的三种标准实现：
        list
        collection.deque
        queue.Queue
    其他实现方法：
        自建链表作为Queue
"""

def queueByList():
    """
        用list实现Queue
    """
    queue_list = []
    queue_list.append("a")
    queue_list.append("b")
    queue_list.append("c")
    print(queue_list)
    queue_list.pop(0)
    print(queue_list)
    queue_list.pop(1)
    print(queue_list)



from collections import deque
def queueByDeque():
    """
        用collection.deque实现
    """
    queue_Deque = deque()
    queue_Deque.append("1st")
    queue_Deque.append("2nd")
    queue_Deque.append("3rd")
    queue_Deque.append("4th")
    print(*queue_Deque)
    print(queue_Deque.popleft())
    print(queue_Deque.pop())
    print(*queue_Deque)
    queue_Deque.clear()


from queue import Queue
def queueByQueue():
    """
        用queue.Queue实现
        left : front
        right : rear
    """
    q = Queue(maxsize=3)
    print(q.qsize())
    q.put("1st")
    print("Full's Truth Value:", q.full())
    print("Now the Queue's Address:", q)
    print("Input Other Value In Queue.")
    q.put("2nd")
    q.put("3rd")
    print("Now Full's Truth Value:", q.full())
    print("Output Other Value In Queue.")
    print(q.get())
    print(q.get())
    print("Now Empty's Truth Value:", q.empty())
    print(q.get())
    print("Output Other Value In Queue.")
    print("Now Full's Truth Value:", q.full())
    print("Now Empty's Truth Value:", q.empty())


"""
    实现双链表Doubly Linked List
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.prev = None

class NodeOneWay:
    def __init__(self,data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = NodeOneWay("head")    # 初始化添加一个["head"|·]结点
        self.size = 0   # 只有头结点时栈长记0

    def __str__(self):
        """
            栈值Str化输出
            E.X.:Input:[ head | · ]->[ data1 | · ]->[ data2 | None ]
                 Output:"data1->data2"
        """
        cur = self.head.next
        out = ""    # 输出值在空栈时为空
        while cur :
            out += str(cur.data) + "->"
            cur = cur.next
        return out[:-2]  # 输出时去掉最后一个->

    def getSize(self)->int:
        """
            返回栈长
        """
        return self.size

    def isEmpty(self)->bool:
        """
            返回是否空栈的逻辑值
        """
        return self.size == 0

    # Get the top item of the stack
    def peek(self):
        """
            返回栈顶元素值
        """
        if self.isEmpty():
            return None  # 空栈时返回None
        return self.head.next.value

    def push(self, value):
        """
            压栈：将value添加在栈顶
        """
        node = NodeOneWay(value)
        node.next = self.head.next  # 新节点指向原头结点的后继节点(原栈顶)
        self.head.next = node  # 头结点指向新节点
        self.size += 1  # 栈长+1

    def pop(self):
        """
            出栈：栈顶元素节点删除，返回栈顶元素value
        """
        if self.isEmpty():  # 栈空时抛出异常
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = remove.next    # 头结点指向原栈顶元素后继
        self.size -= 1
        return remove.data


class QueueByDLL:
    def __init__(self):
        """
        定义两个指针front和rear;
        定义size作为元素个数属性。
        """
        self.front = None
        self.rear = None
        self.size = 0

    def __str__(self):
        """
        打印队列元素。
        :return:
        """
        if self.isEmpty():
            return "Queue is Empty, Can Not be print!"
        else:
            temp = self.front
            result = str(temp.data)
            while temp.next is not None:
                temp = temp.next
                result += (" <- "+str(temp.data))
            del temp
            return result

    def putAtFront(self, data):
        """
        实现头入，对于标准队列非法。
        无返回值!
        :param data:
        """
        if self.isEmpty():
            temp = Node(data)
            self.front = temp
            self.rear = self.front
            del temp
            self.size += 1
        else:
            temp = Node(data)
            temp.next = self.front
            self.front = temp
            del temp
            self.size += 1

    def putAtRear(self, data):
        """
        实现尾入，作为标准队列的入队函数被调用。
        无返回值!
        :param data:
        """
        if self.rear is None:
            temp = Node(data)
            self.rear = temp
            self.front = self.rear
            del temp
            self.size += 1
        else:
            temp = Node(data)
            self.rear.next = temp
            temp.prev = self.rear
            self.rear = self.rear.next
            del temp
            self.size += 1

    def getAtFront(self):
        """
        实现头出，作为标准队列出队函数被调用。
        返回None或头部值!
        :return:
        """
        if self.isEmpty():
            return None
        else:
            temp = self.front.data
            self.front = self.front.next
            self.size -= 1
            if not self.isEmpty():
                self.front.prev = None
            return temp

    def getAtRear(self):
        """
        实现尾出，作为标准队列非法。
        返回None或尾部值!
        :return:
        """
        if self.isEmpty():
            return None
        else:
            temp = self.rear.data
            self.rear = self.rear.prev
            self.rear.next = None
            self.size -= 1
            return temp

    def enqueue(self,data):
        """
        队列入队，使用putAtRear函数进行尾入。
        无返回值!
        :param data:
        """
        self.putAtRear(data)

    def dequeue(self):
        """
        队列出队，使用getAtFront函数进行头出。
        返回头部取出值!
        :return:
        """
        return self.getAtFront()

    def first(self):
        """
        返回队列头部值。
        不改动队列值!
        :return:
        """
        return self.front.data

    def last(self):
        """
        返回队列尾部值，对于标准队列非法。
        不改动队列值!
        :return:
        """
        return self.rear.data

    def isEmpty(self):
        """
        判断队列是否为空，返回布尔值。
        :return:
        """
        if self.size == 0:
            return True
        return False


    def kPosReverse(self,k):
        """
            对队列前K元素进行翻转
            # 将front开始前k项出队组成新队列，然后在原队列putAtFront新队列
        """
        temp = QueueByDLL()
        for i in range(k):
            # 对前k位temp头出元素进入temp队列尾部
            temp.enqueue(self.getAtFront())
        for i in range(k):
            # 对temp头出值插入self的头部
            self.putAtFront(temp.getAtFront())
        del temp

    def kPosReverseByStack(self,k):
        """
        利用栈对前k位翻转
        E.X.: Reverse Front 3 Element For Queue:1 <- 2 <- 3 <- 4 <- 5
            (1)Stack: 3 -> 2 -> 1 | Queue: 4 <- 5
            (2)Queue: 4 <- 5 <- 3 <- 2 <- 1
            (3)Queue: 3 <- 2 <- 1 <- 4 <- 5
        :param k:
        :return:
        """
        temp = Stack()
        for i in range(k):
            temp.push(self.getAtFront())
        for i in range(k):
            self.enqueue(temp.pop())
        del temp
        for i in range(self.size-k):
            self.enqueue(self.getAtFront())






def queueByDoublyLinkedList():
    """
        用双链表实现Queue
    """
    q = QueueByDLL()
    print("Queue Size :",q.size)

    print("Now Put Some Elements Into Queue")
    q.enqueue("2nd")
    q.putAtRear("3rd")
    q.putAtFront("1st")
    q.enqueue("4th")
    q.enqueue("5th")
    q.enqueue("6th")

    print("    Queue first element :", end=" ")
    print(q.first())
    print("    Now Queue element are:", end=" ")
    print(q)
    """
    print("Get One Element Out Of Queue")
    q.dequeue()
    """
    print("Reverse Front 3 Data.")
    q.kPosReverse(3)
    print("    Now Queue element are:", end=" ")
    print(q)

    print("Reverse Front 3 Data By Stack.")
    q.kPosReverseByStack(3)
    print("    Now Queue element are:", end=" ")
    print(q)

    """
    print("Reverse Front 2 Data.")
    q.kPosReverse(2)
    print("    Now Queue element are:", end=" ")
    print(q)

    print("Reverse Front 4 Data.")
    q.kPosReverse(4)
    print("    Now Queue element are:", end=" ")
    print(q)

    print("Reverse Front 5 Data.")
    q.kPosReverse(5)
    print("    Now Queue element are:", end=" ")
    print(q)
    """


"""
if __name__ == '__Main__':
    queueByList()
    queueByDeque()
    queueByQueue()
    queueByDoublyLinkedList()
"""
queueByDoublyLinkedList()












